<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 给定一个 haystack 字符串和一个 needle 字符串，
        // 在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

        // 思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串
        function strStr(haystack, needle) {
            let n = needle.length;
            let n1 = needle[0];
            for (var i = 0; i < haystack.length - n + 1; i++) {
                if (haystack[i] === n1) {
                    if (needle == haystack.substr(i, n)) {
                        return n
                    }
                }
                if (i == haystack.length - n) {
                    return -1
                }
            }
        }
        console.log(strStr('hello', 'a'));

        // 方法: 双指针优化


        // 方法 KMP 
        // KMP主要应用在字符串匹配上。
        // KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
        // 所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
        function strKmp(haystack, needle) {
            var h = haystack.length;
            var n = needle.length;
            // 如何构建二维数组
            var dp = new Array();
            for (var m = 0; m < n; m++) {
                dp[m] = [];
                for (var y = 0; y < 256; y++) {
                    dp[m][y] = 0
                }
            }
            console.log(dp);

            dp[0][needle.charCodeAt(0)] = 1;
            // 构建状态
            var X = 0;
            for (var i = 0; i < n; i++) {
                for (var c = 0; c < 256; c++) {
                    // dp[i][c] = next
                    if (c == needle.charCodeAt(i)) {
                        // 状态推进
                        dp[i][c] = i + 1;
                    } else {
                        //状态重启  
                        // 委托X计算重启位置
                        // console.log(X);
                        dp[i][c] = dp[X][c];
                    }
                }
                // 更新影子状态
                X = dp[X][needle.charCodeAt(i)];
            }
            console.log(dp);
            var j = 0;
            for (var i = 0; i < h; i++) {
                j = dp[j][haystack.charCodeAt(i)];
                if (j === n) {
                    return i - n + 1
                }
            }
            return -1
        }
        console.log(strKmp('hello', 'el'));

    </script>
</body>

</html>